
public class BTreePlus {

	private  int minGap ;
	private  int minGapAux ;
	private int t;
	private node root;
	private int gap;
	private BloomFilter filter;
	private int order;
	
	public BTreePlus(int t){
		this.t = t;
		this.root = new node(t,true);
		this.minGap = -1;
		this.minGapAux = -1 ;
		this.gap = - 1;
		this.filter = new BloomFilter(2.0 , 1000 ,2 );
		this.order = -1;
	}
	
	public int Min_gap(){
		return this.gap;
	}
	
	public String printLeafs (){
		String str = "";
		node tempNode = new node(this.root);
		if (this.root != null){
			
			while (tempNode.getSonInIndex(0) != null){
				tempNode = tempNode.getSonInIndex(0);
			}
			
			while (tempNode != null){
				
				for (int i = 0 ; i < tempNode.getSize() ; i++){
					if (i < tempNode.getSize() - 1){
						str = str + tempNode.getDataOfIndex(i) + ",";
					}else{
						str = str + tempNode.getDataOfIndex(i);
					}
					
				}
				tempNode = tempNode.getNext();
				if(tempNode != null){
					str = str + "#";
				}
				
				
			}
		}
		return str;
		
		
	}
	
	
	
	public boolean search (int searchCandidate){
		return search(searchCandidate , false);
		
	}
	
	public int Order(int x){
		search(x,true);
		return this.order;
	}
	
	
	public boolean search(int searchCandidate ,boolean orderSearch){
		boolean found = false;
//		if (this.filter.containsTheNumber(searchCandidate)){
			NodeNValue search = new NodeNValue();
			search = NodeSearch(root, searchCandidate);
			found = search.found;
			if (orderSearch = true){
				this.order = search.order;
//			}
		}
		return found;
		
	}
	
	private static NodeNValue NodeSearch(node n , int searchCandidate){
		NodeNValue orderAndSearchResoult = new NodeNValue();
		boolean found = false;
		boolean foundLessOrEqual = false;
		int i = 0;
		int orderHelper = 0;
		
		if ( null == n ){
			orderAndSearchResoult.found = false;
			return orderAndSearchResoult;
		}
			
		
		while ( ( !found 			)&&
				( i < n.getSize() 	)&& 
				( !foundLessOrEqual ) ){
			if ( searchCandidate <= n.getDataOfIndex(i)){
				if (n.isLeaf()){
					if (n.getDataOfIndex(i) == searchCandidate){
						found = true;
						orderAndSearchResoult.found = true;
						orderAndSearchResoult.n = n;
						orderHelper = i + 1;
						node temp = new node(n);
						
						while (temp.getPrevious() != null){
							temp = temp.getPrevious();
							orderHelper = orderHelper + temp.getSize();
							
						}
						orderAndSearchResoult.order = orderHelper;
						
					}
				}else{
					foundLessOrEqual = true;
					orderAndSearchResoult = NodeSearch(n.getSonInIndex(i), searchCandidate);			//Recursively search in the needed sons.
					found = orderAndSearchResoult.found;
				}
			}
			i++;
		}
		//special case , if our value is greater then the all of the data in the node
		if (!found 				&&
			i == n.getSize()	&&
			!foundLessOrEqual	&&
			!n.isLeaf()){
			
			orderAndSearchResoult = NodeSearch(n.getSonInIndex(i), searchCandidate);			//Recursively search in the needed sons.
			found = orderAndSearchResoult.found;
		}
		
		
		return orderAndSearchResoult;
	}
	public void insert(int x){
//		this.filter.addNumber(x);
		NodeNValue newRigthHand = insert(x, root);
		this.minGapAux = newRigthHand.minGap;
		updateMinGap(this.gap, minGapAux);
		
//		this.gap = newRigthHand.minGap;
		
		if ( newRigthHand.n != null ){
			node newRoot = new node(this.t,false);
			newRoot.setData( 0, newRigthHand.value );
			newRoot.setSon( 0, this.root );
			newRoot.setSon( 1, newRigthHand.n );
			newRoot.incSize();
			
			this.root = newRoot;
		}
	}
	private  void updateMinGap(int gap , int minGapAux){
		if (this.gap != -1 && this.minGapAux > 0 && this.minGapAux < this.gap){
			this.gap = this.minGapAux;
		}
		if (this.gap == -1){
			this.gap = this.minGapAux;
		}
		
	}
	
	private static NodeNValue insert(int insertValue , node n){
		NodeNValue newSon = new NodeNValue();
		
		boolean foundLessOrEqual = false;
		int i = 0;
		while ( ( i < n.getSize() 	)&& 
				( !foundLessOrEqual ) ){
			
			if ( insertValue <= n.getDataOfIndex(i)){
				foundLessOrEqual = true;
				
				if (n.isLeaf()){
					if (n.isFull()){
						newSon = n.split(insertValue, null, false);
						// newSon.n = rightHalf;
						// newSon.value =n.getDataOfIndex(n.getSize() - 1); 
					}else{
						NodeNValue nodeAndValue = new NodeNValue();
						nodeAndValue.n 		= null;
						nodeAndValue.value 	= insertValue;
						newSon.minGap = n.insertValueFixSons( nodeAndValue );
//						updateMinGap(minGap , minGapAux);
					}
				}else{
					newSon = insert(insertValue, n.getSonInIndex(i));
					
					if ( newSon.n != null ){
						if (n.isFull()){
							newSon = n.split(newSon.value, newSon.n, true);
						}else{
							n.insertValueFixSons( newSon );
							newSon.nPrev = newSon.n.getPrevious();
							newSon.nPrev = newSon.n.getNext();
							newSon.n = null;
						}
					}
				}
			}
			i++;
		}
		//special case , if our value is greater then the all of the data in the node
		if ( ( i == n.getSize()		) &&
			 ( !foundLessOrEqual	) ){
			if ( n.isLeaf() )
			{
				if (n.isFull()){
					newSon = n.split(insertValue, null, false);
//					minGapAux = newSon.minGap;
//					updateMinGap(minGap , minGapAux);
//					newSon.minGap = minGap;
				}else{
					NodeNValue nodeAndValue 	= new NodeNValue();
					nodeAndValue.n 				= null;
					nodeAndValue.value 			= insertValue;
					newSon.minGap 				= n.insertValueFixSons( nodeAndValue );
//					updateMinGap(minGap , minGapAux);
//					newSon.minGap = minGap;
					
				}
			}else{
				newSon = insert(insertValue, n.getSonInIndex(i));
				foundLessOrEqual = true;
				
				if ( newSon.n != null ){
					if (n.isFull()){
						newSon = n.split(newSon.value, newSon.n, true);
					}else{
						n.insertValueFixSons( newSon );
						
						newSon.n = null;
					}
				}
			}
			
		}
		
		return newSon;

	}
}
